import "sort"

/*
 * @lc app=leetcode.cn id=15 lang=golang
 *
 * [15] 三数之和
 */

// @lc code=start
func threeSum(nums []int) [][]int {
	sort.Ints(nums)
	l:=len(nums)
	res:=[][]int{}
	for base:=0;base<l-2;base++{
		if base>0 && nums[base]==nums[base-1]{
			continue
		}

		start:=base+1
		end:=l-1
		target:=0-nums[base]

		for start<end{
			if nums[start]+nums[end]==target{
				res = append(res,[]int{nums[start],nums[end],nums[base]})
				for start<end && nums[start]==nums[start+1]{
					start++
				}
				for start<end && nums[end]==nums[end-1]{
					end--
				}

				start++
				end--

			}else if nums[start]+nums[end]<target{
				start++
			}else{
				end--
			}
		}
	}

	return res
}


// @lc code=end

